home *** CD-ROM | disk | FTP | other *** search
/ Aminet 45 / Aminet 45 (2001)(GTI - Schatztruhe)[!][Oct 2001].iso / Aminet / dev / src / sort.lha / Shell_Sort.c < prev    next >
C/C++ Source or Header  |  2001-08-22  |  2KB  |  81 lines
  1. /*
  2. **  Shellsort Algorithmus in C
  3. **  Norman Walter, Universität Stuttgart
  4. **  Datum: 22.8.2001
  5. **
  6. **  Shellsort ist eine einfache Erweiterung von Insertion Sort,
  7. **  bei dem eine Erhöhung der Geschwindigkeit dadurch erzielt
  8. **  wird, daß ein Vertauschen von Elementen ermöglicht wird,
  9. **  die weit voneinander entfernt sind.
  10. **
  11. **  Eigenschaften: Shellsort führt niemals mehr als
  12. **  N^(2/3) Vergleiche aus.
  13. */
  14.  
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17.  
  18. #define maxN 100
  19.  
  20. void display(int a[], int n)
  21. {
  22.  
  23. /* Gibt komplettes Array aus */
  24.  
  25.    int i;
  26.    for (i = 1; i <= n; i++) printf ("%d ", a[i]);
  27.     printf("\n");
  28. }
  29.  
  30. void shellsort(int a[], int N)
  31.  
  32. /* Shellsort Algorithmus */
  33.  
  34.   {
  35.     /* Durch das h-Sortieren für große h können wir Elemente
  36.     ** im Feld über größere Entfernungen bewegen und damit
  37.     ** eine h-Sortierung für kleinere Werte von h erleichtern.
  38.     ** Indem man eine solche Prozedur für eine beliebige Folge
  39.     ** von Werten von h anwendet, die mit 1 endet, erhält man
  40.     ** eine sortierte Datei.
  41.     */
  42.  
  43.     int i, j, h, v;
  44.     for (h = 1; h <= N/9; h = 3*h+1);
  45.         for ( ; h > 0; h /= 3)
  46.             for (i = h+1; i <= N; i +=1)
  47.                 {
  48.                     v = a[i]; j = i;
  49.                     while (j>h && a[j-h]>v)
  50.                         { a[j] = a[j-h]; j -= h; }
  51.                     a[j] = v;
  52.                     display(a,N);
  53.                 }
  54.   }
  55.  
  56. int main()
  57.  
  58. {
  59.  
  60. int i;
  61. int n, a[maxN+1];
  62.  
  63. /* Schleife erzeugt zufällige Permutation */
  64.  
  65.   for(n=0; n<=15; n++)
  66.   {
  67.     i = rand() % 10;
  68.     a[n+1] = i;
  69.     printf ("%d ",i);
  70.   }
  71.  
  72. printf("\n");
  73.  
  74. /* Array sortieren */
  75.  
  76. a[0] = 0; shellsort(a,n);
  77.  
  78. return(0);
  79.  
  80. }
  81.